#include<vector>
using namespace std;
//class Solution {
//    struct Data {
//        int remain;
//        int need;
//        Data(int remain_, int need_):remain(remain_), need(need_){
//
//        }
//    };
//public:
//    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
//        vector<Data>vec;
//        int start = 0;
//        int index = 0;
//        int remain = 0;
//        while (index < gas.size()) {
//            remain += gas[index];
//            if (remain < cost[index]) {
//                vec.emplace_back(remain, cost[index]);
//                remain = 0;
//                start = index + 1;
//                if (index == gas.size() - 1)
//                    return -1;
//            }else
//                remain -= cost[index];
//            ++index;
//        }
//        for (int i = 0; i < vec.size(); ++i) {
//            remain += vec[i].remain-vec[i].need;
//            if (remain < 0) {
//                start = -1;
//                break;
//            }
//        }
//        return start;
//    }
//};


class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int need = 0;
        int remain = 0;
        int start = 0;
        for (int i = 0; i < gas.size(); ++i) {
            remain += gas[i] - cost[i];
            if (remain < 0) {
                start = i + 1;
                need -= remain;
                remain = 0;
            }
        }
        if (remain < need)
            start = -1;
        return start;

    }
};